/*
 *      Filename: quick_sort.c
 *       Version: 0.1.0
 *   Description: 快速排序，选出第K小的值
 *
 *        Author: wuyaowei
 *          Date: 2020-07-20
 *
 */

#include <stdio.h>

int partition(int a[], int p, int r) {
    int pivot = a[r];
    int s = r;  //记录分区点下标

    for(int i = p; i <= r; i++) {
        if ((a[i] > pivot)  && s > i) {
	    a[s] = a[i];
	    a[i] = pivot;
	    s = i;
	}
    }
    return s;
}


void quick_sort(int a[], int p, int r) {
    if (p >= r) return;
    
    int q = partition(a, p, r);
    
    quick_sort(a, p, q-1);
    quick_sort(a, q+1, r);
}


void main() {
    int a[] = {-4, 2, 10, 9, 8, 7, 6};
    int len = sizeof(a)/sizeof(int);
    quick_sort(a, 0, len-1);
    printf("第三小的值是：%d\n", a[2]);
}
